package com.hqq.sort.queue;

/**
 * MaxPriorityQueue
 * 最大优先级队列
 * 主要功能:
 * 删除最大元素和插入元素
 * Created by heqianqian on 2017/8/4.
 */
public class MaxPriorityQueue<T extends Comparable<T>> {

    private T[] priorityQueue;

    private int count = 0;

    public MaxPriorityQueue() {
    }

    @SuppressWarnings("unchecked")
    public MaxPriorityQueue(int maxN) {
        priorityQueue = (T[]) new Comparable[maxN + 1];
    }

    public MaxPriorityQueue(T[] priorityQueue) {
        this.priorityQueue = priorityQueue;
    }

    /**
     * 插入元素
     */
    public void insert(T key) {
        priorityQueue[++count] = key;
        swim(count);
    }

    /**
     * 返回最大元素
     */
    public T max() {
        return null;
    }

    /**
     * 删除最大元素并返回
     */
    public T delMax() {
        return null;
    }

    /**
     * 队列是否为空
     */
    public boolean isEmpty() {
        return count == 0;
    }

    /**
     * 返回队列元素个数
     */
    public int size() {
        return count;
    }

    /**
     * 由下而上的堆有序化上浮
     */
    private void swim(int count) {
        while (count > 1 && less(count / 2, count)) {
            exchange(count / 2, count);
            count = count / 2;
        }
    }

    /**
     * 由下而上的堆有序化下沉
     */
    private void sink(int count) {
       while (2*count<=this.count){
           int j = 2*count;
           if (j<this.count&&less(j,j+1)){
               j++;
           }
           if (!less(count,j)){
               break;
           }
           exchange(count,j);
           count = j;
       }
    }

    /**
     * 比较i和j下标对应元素的大小
     */
    private boolean less(int i, int j) {
        return priorityQueue[i].compareTo(priorityQueue[j]) < 0;
    }

    /**
     * 交换队列中的i和j下标对应的元素
     */
    private void exchange(int i, int j) {
        T t = priorityQueue[i];
        priorityQueue[i] = priorityQueue[j];
        priorityQueue[j] = t;
    }
}
